package main;

import java.util.*;

public class MaximalSolutionSolver {

    public static void main(String[] args) {
        // 示例输入：方程系数和目标值
        double[] coefficients = {1/20.0, 1/33.0, 3/20.0}; // 例如 1/20, 1/33, 3/20
        double a = 1.0;                                   // 目标值
        int[] minValues = {7, 10, 1};                     // x≥7, y≥10, z≥1
        solveMaximalSolutions(coefficients, a, minValues);
    }

    public static void solveMaximalSolutions(double[] n, double a, int[] minValues) {
        final int SCALE = 1000; // 小数精度控制（三位小数）
        int k = n.length;

        // 1. 转换为整数问题（放大 SCALE 倍）
        int[] N = new int[k];
        int sumMin = 0;
        for (int i = 0; i < k; i++) {
            N[i] = (int) Math.round(n[i] * SCALE); // 系数转换为整数
            sumMin += N[i] * minValues[i];         // 计算最小值总和
        }

        int A = (int) Math.round(a * SCALE);       // 目标值转换为整数
        int A_prime = A - sumMin;                  // 转换后的目标值

        if (A_prime <= 0) {
            System.out.println("无解：变量取最小值时已不满足不等式");
            return;
        }

        // 2. 动态规划求解非负整数解
        Map<Integer, List<int[]>> dp = new HashMap<>();
        dp.put(0, new ArrayList<>());
        dp.get(0).add(new int[k]); // 初始解：所有 xi' = 0

        for (int i = 0; i < k; i++) {
            int Ni = N[i];
            Map<Integer, List<int[]>> newDp = new HashMap<>();

            for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
                int currentSum = entry.getKey();
                List<int[]> combs = entry.getValue();

                for (int[] comb : combs) {
                    int maxM = (A_prime - 1 - currentSum) / Ni; // 最大可添加次数
                    for (int m = 0; m <= maxM; m++) {
                        int newSum = currentSum + m * Ni;
                        int[] newComb = Arrays.copyOf(comb, k);
                        newComb[i] += m;

                        if (newSum >= A_prime) continue;

                        newDp.computeIfAbsent(newSum, key -> new ArrayList<>()).add(newComb);
                    }
                }
            }
            dp = newDp;
        }

        // 3. 收集严格小于目标的解
        List<int[]> solutions = new ArrayList<>();
        for (Map.Entry<Integer, List<int[]>> entry : dp.entrySet()) {
            if (entry.getKey() < A_prime) {
                solutions.addAll(entry.getValue());
            }
        }

        // 4. 过滤极大解：至少存在一个变量加1后总和 ≥ A_prime
        List<int[]> maximalSolutions = new ArrayList<>();
        for (int[] comb : solutions) {
            boolean isMaximal = false;
            for (int i = 0; i < k; i++) {
                if (N[i] == 0) continue; // 跳过 ni=0 的变量（无法触发不等式失效）

                int tempSum = 0;
                for (int j = 0; j < k; j++) {
                    tempSum += (j == i) ? N[j] * (comb[j] + 1) : N[j] * comb[j];
                }
                if (tempSum >= A_prime) {
                    isMaximal = true;
                    break;
                }
            }
            if (isMaximal) maximalSolutions.add(comb);
        }

        // 5. 转换为原始变量并输出
        if (maximalSolutions.isEmpty()) {
            System.out.println("无满足条件的解");
        } else {
            System.out.println("满足条件的解（共 " + maximalSolutions.size() + " 种）：");
            for (int[] comb : maximalSolutions) {
                System.out.print("x = [");
                double sum = 0;
                for (int i = 0; i < k; i++) {
                    int value = comb[i] + minValues[i]; // 恢复原始变量 x_i = x'_i + min
                    System.out.print(value + (i < k - 1 ? ", " : ""));
                    sum = sum + (comb[i] * n[i]);
                }
                System.out.println("]");
            }
        }
    }
}